package medium

import (
	. "GoLeetcode/common"
)

/*
时间复杂度:O(N)
空间复杂度:O(K) hash表所需要的内存
*/

func lengthOfLongestSubstringKDistinct(s string, k int) int {
	hash := make(map[byte]int)
	left, right := 0, 0
	ans := 0
	for right < len(s) {
		hash[s[right]]++
		for len(hash) > k {
			hash[s[left]]--
			if hash[s[left]] == 0 {
				delete(hash, s[left])
			}
			left++
		}
		ans = Max(ans, right-left+1)
		right++
	}
	return ans
}
